/*

插入排序与冒泡排序的区别，冒泡排序是先确定最右边的元素；而插入排序是将新元素 从右到左逐个与已排好序的其他元素对比然后找到合适的位置插入

插入排序：稳定排序，当 arr[j] > k 时才交换，相等时不交互
流程：外层循环从1 to n-1, 每次选取当前遍历的元素与前i-1个已排好序的元素进行比较（从右到左，然后到合适的位置插入）
算法时间复杂度
1、最优：O(n), 数组恰好有序，插入每个元素时都只跟前一个元素比一次
2、平均：O(n^2)  最少比较n-1次，最多比较 (n-1)*n/2; 所以一共有 (n-1)*n/2 - (n-1) + 1种情况， 每种情况的比较次数为：n-1, n, n+1, .....
3、最差：O(n^2), 第i个元素需要比较i - 1次，1 + 2 + ... + n - 1

空间复杂度：O(1)
*/
package stable_sort

func InsertSort(arr []int) []int {
	if arr == nil || len(arr) == 0 {
		return []int{}
	}
	for i := 1; i < len(arr); i++ {
		// 记录当前需要排序元素的值
		k := arr[i]
		j := i - 1
		for ; j >= 0 && arr[j] > k; j-- {
			arr[j+1] = arr[j]
		}
		arr[j+1] = k
	}
	return arr
}
